Recursion এবং Tail Recursion এর প্রয়োগ

Recursion এবং Tail Recursion এর প্রয়োগ

ক্লোজারে (Clojure) এবং অন্যান্য ফাংশনাল প্রোগ্রামিং ভাষায় রিকার্সন (Recursion) খুবই গুরুত্বপূর্ণ একটি কনসেপ্ট। এটি এমন একটি পদ্ধতি যেখানে একটি ফাংশন নিজেই নিজেকে কল করে একটি নির্দিষ্ট শর্ত পূরণ না হওয়া পর্যন্ত। তদ্ব্যতীত, টেইল রিকার্সন (Tail Recursion) রিকার্সনের একটি বিশেষ রূপ, যা কার্যক্ষমতাকে উন্নত করতে সাহায্য করে।

রিকার্সন (Recursion) কী?

রিকার্সন হল এমন একটি প্রোগ্রামিং পদ্ধতি, যেখানে একটি ফাংশন নিজেই নিজেকে কল করে, এবং প্রতিবারই একটি নির্দিষ্ট শর্তের ভিত্তিতে নিজেকে পুনরাবৃত্তি করে। রিকার্সন সাধারণত তখন ব্যবহার করা হয় যখন সমস্যা একটি নির্দিষ্ট অংশে বিভক্ত করা যায় এবং প্রতিটি অংশে একই লজিক প্রয়োগ করা যায়।

উদাহরণ: Factorial গণনা

নিচের উদাহরণে, একটি ফাংশন factorial তৈরি করা হয়েছে, যা রিকার্সন ব্যবহার করে একটি সংখ্যার ফ্যাক্টরিয়াল গণনা করে:

(defn factorial [n]
  (if (<= n 1)
    1
    (* n (factorial (dec n)))))

এখানে, factorial ফাংশনটি নিজেই নিজেকে কল করে যতক্ষণ না n এর মান 1 বা তার চেয়ে কম হয়। এই ফাংশনটি n এর মানকে প্রতিবার 1 করে কমায় এবং শেষ পর্যন্ত ফ্যাক্টরিয়াল রিটার্ন করে।

টেইল রিকার্সন (Tail Recursion)

টেইল রিকার্সন একটি বিশেষ ধরনের রিকার্সন, যেখানে ফাংশন কলের শেষে কোনো অতিরিক্ত অপারেশন নেই। এতে প্রতিটি রিকার্সিভ কল ফাংশনের শেষ অপারেশন হিসেবে কাজ করে, অর্থাৎ, এর পরে আর কোনো অপারেশন সম্পন্ন হয় না। এই ধরনের রিকার্সনে স্ট্যাকের ওপর অতিরিক্ত মেমোরি লোড পড়ে না, এবং কার্যক্ষমতা বৃদ্ধি পায়।

Clojure এ টেইল রিকার্সনের জন্য recur ব্যবহার

ক্লোজারে টেইল রিকার্সন বাস্তবায়নের জন্য recur কীওয়ার্ড ব্যবহার করা হয়। recur রিকার্সিভ কলের ক্ষেত্রে লুপ হিসেবে কাজ করে এবং নতুন স্ট্যাক ফ্রেম তৈরি না করে পূর্বের ফ্রেমটি পুনরায় ব্যবহার করে, যা মেমোরি সাশ্রয় করে।

উদাহরণ: টেইল রিকার্সনের মাধ্যমে Factorial গণনা

(defn factorial [n]
  (let [helper (fn [n acc]
                 (if (<= n 1)
                   acc
                   (recur (dec n) (* acc n))))]
    (helper n 1)))

এই উদাহরণে helper নামের একটি অভ্যন্তরীণ ফাংশন ব্যবহার করা হয়েছে, যা recur দিয়ে টেইল রিকার্সন কার্যকর করে। এখানে acc (accumulator) প্যারামিটারটি ফলাফলের জন্য ব্যবহৃত হয়, এবং প্রতিটি রিকার্সিভ কলের শেষে recur স্ট্যাকের লোড না বাড়িয়ে একই স্ট্যাক ফ্রেমে পুনরাবৃত্তি করে।

রিকার্সন বনাম টেইল রিকার্সনের পার্থক্য

ফিবোনাচি সিরিজের উদাহরণ

নিচে দুটি পদ্ধতিতে ফিবোনাচি সিরিজ গণনার উদাহরণ দেওয়া হলো - সাধারণ রিকার্সন এবং টেইল রিকার্সন:

সাধারণ রিকার্সন দিয়ে ফিবোনাচি সিরিজ

(defn fibonacci [n]
  (if (<= n 1)
    n
    (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))

এই ফাংশনটি প্রতিটি রিকার্সিভ কলের জন্য নতুন ফ্রেম তৈরি করে, যা বড় n এর জন্য স্ট্যাক ওভারফ্লো ঘটাতে পারে।

টেইল রিকার্সন দিয়ে ফিবোনাচি সিরিজ

(defn fibonacci [n]
  (let [helper (fn [a b n]
                 (if (zero? n)
                   a
                   (recur b (+ a b) (dec n))))]
    (helper 0 1 n)))

এই উদাহরণে helper ফাংশনের মধ্যে recur ব্যবহার করা হয়েছে, যা টেইল রিকার্সনের মাধ্যমে একই স্ট্যাক ফ্রেমে কার্যকর হয় এবং মেমোরি সাশ্রয় করে।

সারসংক্ষেপ

1. রিকার্সন সাধারণত একটি ফাংশনের নিজেকে পুনরাবৃত্তি করার পদ্ধতি, যেখানে প্রতিটি রিকার্সিভ কল নতুন স্ট্যাক ফ্রেম তৈরি করে।
2. টেইল রিকার্সন এমন রিকার্সন যেখানে ফাংশনের শেষ অপারেশনটি রিকার্সিভ কল থাকে, ফলে মেমোরি ব্যবহার কম হয় এবং কার্যক্ষমতা বৃদ্ধি পায়।
3. recur ক্লোজারে টেইল রিকার্সন বাস্তবায়নের জন্য ব্যবহৃত হয়, যা নতুন স্ট্যাক ফ্রেম তৈরি না করে একই ফ্রেম পুনরায় ব্যবহার করে।

ক্লোজারে কার্যক্ষমতা বৃদ্ধির জন্য টেইল রিকার্সন একটি শক্তিশালী কৌশল, বিশেষত বড় রিকার্সিভ অপারেশনের জন্য।